package com.zhupf.binaryTree;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author zhupf
 * @date 2023年12月04日 10:48
 * @
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 *
 * 105. 从前序与中序遍历序列构造二叉树
 */
public class BuildTree {

    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        BuildTree buildTree = new BuildTree();
        buildTree.buildTree(preorder,inorder);

    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer,Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i],i);
        }
        return process(preorder,inorder,0,inorder.length-1,0,inorder.length-1,inorderMap);
    }

    private TreeNode process(int[] preorder, int[] inorder,int preLeft,int preRight , int inLeft,int inRihgt,Map<Integer,Integer> inorderMap){
        if(inLeft>inRihgt){
            return null;
        }
        int rootVal = preorder[preLeft];
        Integer inRootIdx = inorderMap.get(rootVal);
        int leftNum = inRootIdx - inLeft;
        return new TreeNode(rootVal,process(preorder,inorder,preLeft+1,preLeft+leftNum,inLeft,inRootIdx-1,inorderMap),
                process(preorder,inorder,preLeft+leftNum+1,preRight,inRootIdx+1,inRihgt,inorderMap)
                );
    }

    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        Deque<TreeNode> stk = new LinkedList<>();
        TreeNode root = new TreeNode(preorder[0]);
        stk.push(root);
        int index = 0;
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = stk.peek();
            if(inorder[index] != node.val){
                node.left = new TreeNode(preorder[i]);
                stk.push(node.left);
            }else {
                while (!stk.isEmpty() && stk.peek().val == inorder[index]){
                    index++;
                    node = stk.poll();
                }
                node.right = new TreeNode(preorder[i]);
                stk.push(node.right);
            }
        }
        return root;
    }

}
